//给你一个字符串 s，找到 s 中最长的回文子串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
// 示例 3：
//
//
//输入：s = "a"
//输出："a"
//
//
// 示例 4：
//
//
//输入：s = "ac"
//输出："a"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母（大写和/或小写）组成
//
// Related Topics 字符串 动态规划
// 👍 3631 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
package main

import "fmt"

func main() {
	fmt.Println(longestPalindrome("babad"))
	fmt.Println(longestPalindrome2("babad"))
}

// 中心拓展法
func longestPalindrome(s string) string {
	if s == "" {
		return ""
	}
	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		left1, right1 := expandAroundCenter(s, i, i)
		left2, right2 := expandAroundCenter(s, i, i + 1)
		if right1 - left1 > end - start {
			start, end = left1, right1
		}
		if right2 - left2 > end - start {
			start, end = left2, right2
		}
	}
	return s[start:end+1]
}

func expandAroundCenter(s string, left, right int) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1 , right+1 { }
	return left + 1, right - 1
}

// 动态规划
func longestPalindrome2(s string) string {
	if len(s) < 2 {
		return s
	}
	maxLength := 0
	begin := 0
	dp := make([][]bool, len(s))
	for i, _ := range dp {
		dp[i] = make([]bool, len(s))
	}

	// 枚举子串长度
		//为什么要枚举子串长度？因为状态转移过程是通过子串长度的增加而变化的，
		//只有知道了长度为1/2的子串是否为回文串，才能推算出长度为3/4的子串是否为回文串
	for L := 1; L <= len(s); L++ {
		// 枚举左边界
		for i := 0; i < len(s); i++ {
			// 由 j - i + 1 = L可以得出右边界
			j := L + i - 1
			if j >= len(s) {
				 break
			}
			if L == 1 {
				dp[i][j] = true
			} else if L == 2 {
				dp[i][j] = s[i] == s[j]
			} else {
				dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
			}
			if dp[i][j] == true && L > maxLength {
				begin = i
				maxLength = L
			}
		}
	}
	return s[begin:begin+maxLength]
}
//leetcode submit region end(Prohibit modification and deletion)
